package leetcode;

public class FindMedian {

    static int[] array1 = {1, 4, 9, 17, 21};
    static int[] array2 = {8, 10, 14, 25, 29};

    public static void main(String[] args) {
        System.out.println(findMedianSortedArrays(array1, array2));
    }

    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int l1 = nums1.length, l2 = nums2.length;
        int sum = (l1 + l2) % 2;
        int mid = (l1 + l2) / 2;
        if (l1 > 0 && l2 > 0) {
            int i = l1 - 1, j = l2 - 1;
            while (j >= 0) {
                int n1 = nums1[i];
                int n2 = nums2[j];
                if (n1 <= n2) {
                    j--;
                } else {
                    nums1[i] = n1 ^ n2 ^ (nums2[j--] = n1);
                    int k = i - 1;
                    while (k >= 0) {
                        int tmp = nums1[k];
                        if (tmp > nums1[k + 1]) {
                            nums1[k] = tmp ^ n2 ^ (nums1[k + 1] = tmp);
                            k--;
                        } else {
                            break;
                        }
                    }
                }
            }
        }
        if (l1 == l2) {
            return (nums1[l1 - 1] + nums2[0]) / 2.0;
        }
        if (l1 > l2) {
            if (sum == 0) {
                return (nums1[mid] + nums1[mid - 1]) / 2.0;
            } else {
                return nums1[mid];
            }
        }
        if (l1 < l2) {
            int s = l2 - mid;
            if (sum == 0) {
                return (nums2[s - 1] + nums2[s]) / 2.0;
            } else {
                return nums2[s - 1];
            }
        }
        return 0;
    }

    static void out(int[] array1) {
        for (int i = 0; i < array1.length; i++) {
            System.out.print(array1[i]);
            System.out.print(",");
        }
        System.out.println("");
    }
}
